In today's information age, communication networks are often used for interconnecting computers and computer peripherals. A communication network typically includes a number of nodes that interoperate to route protocol messages. The various nodes in the communication network utilize various routing protocols in order to determine the routes that are used to route the protocol messages. Thus, each node is a computer that performs, among other things, various routing protocols in order to route protocol messages.
One type of routing protocol, known as a “link state” routing protocol, determines routes based upon the status of communication links between the various nodes. A link state routing protocol, such as OSPF and IS-IS, requires each node to have complete topology information. Therefore, each node periodically tests the communication links to each of its neighbors and sends a link state advertisement (LSA) protocol message including the link status information to all of the other nodes. Each node computes the routes based upon the link status information received from the other nodes.
When a node receives a LSA protocol message, the node updates its topology information database to include the link status information received in the LSA protocol message, and runs a special algorithm to determine the routes based upon the updated topology information. One well-known algorithm for determining routes is the Dijkstra shortest path algorithm. The Dijkstra shortest path algorithm computes the shortest paths to all destinations from a single source.
In order for the nodes in the communication network to properly route protocol messages, it is important for each node to compute routes in a timely manner. Unfortunately, the Dijkstra shortest path algorithm is computationally intensive, and can take a relatively long time to complete, especially in communication networks having many nodes.
Thus, a technique for reducing the amount of time required to complete the Dijkstra shortest path computation is needed.